Section: New Results

Algebraic methods for geometric problems

New bivariate system solver and topology of algebraic curves

We present in [22] a new approach for solving polynomial systems of two bivariate polynomials with rational coefficients. The tools used in our algorithm are classical (subresultants, Groebner basis, triangular systems, regular chains, RUR (rational univariate representations), modular computation) but they are combined in a new way. We first use a classical approach based on subresultant sequences for decomposing a system into subsystems according to the number of roots (counted with multiplicities) in vertical lines. We then show how the resulting triangular subsystems can be efficiently solved by computing lexicographic Gröbner bases and Rational Univariate Representations (RURs) of these systems. We eventually show how this approach can be performed using modular arithmetic, while remaining deterministic, yielding an algorithm that can take advantage of a parallel implementation. We apply our solver to the problem of computing the topology of algebraic curves using the algorithm Isotop [31] . We show that, on generic curves, our algorithm performs similarly as classical resultant-based algorithms and, on non-generic curves, it performs significantly better than all non-GPU based implementations (it outperforms the curve arrangement of CGAL with factors up to several hundreds). Preliminary experiments also hint that the recent GPU-based approach of Berberich et al. [29] and the multi-thread version of our implementation perform similarly on a standard machine, although our implementation naturally depends on the number of threads.

We also started to work on a generalization of these results to real algebraic curves embedded in dimension 3 and higher.

Counting the number of embeddings of a given rigid graph

We addressed the problem of counting the number of embeddings of a given rigid graph (a graph with edges labeled by distances). Such graphs are still not well understood and appear in several applications such as robot kinematics and structural biology. By modeling the problem as a sparse system of polynomial equations, we could bound the maximal number of embeddings from above with the algebraic mixed volume theory, and bound it from below with stochastic optimization methods. This work submitted in 2010 was accepted and published in the proceedings of the IFToMM 2011 conference [21] .

Description of singularities of a parameterized mechanism

Kinematic design can be seen as an application of rigid graph theory. In collaboration with the IRCCyN laboratory, we worked on the design of parallel mechanisms. We studied in particular the cable robots, a new kind of architecture, which is difficult to understand. The problem is to describe the set of parameters such that the robot doesn't break or lose control. Using tools from algebra, we can describe rigorously the working space of a simple planar cable robot [19] . Work on this subject is promising, and some theory developed for rigid graphs could give other interesting results in kinematic design.

Distance between 3-dimensional terrains

We addressed the problem of computing efficiently the distance between two piecewise-linear bivariate functions $f$ and $g$ defined over a common domain $M$. We focus on the distance induced by the $L_2$-norm, that is ${\parallel f-g\parallel }_2=\sqrt{{\int }_M{(f-g)}^2}$. If $f$ is defined by linear interpolation over a triangulation of $M$ with $n$ triangles, while $g$ is defined over another such triangulation, the obvious naïve algorithm requires $\Theta \left(n^2\right)$ arithmetic operations to compute this distance. We show that it is possible to compute it in $O(nlog{\left(n\right)}^4)$ arithmetic operations, by reducing the algebraic problem to multi-point evaluation of a certain type of polynomials [24] .

Invariant-based predicate evaluation strategies

We have worked on formalizing polynomial evaluation strategies of geometric predicates using algebraic invariant theory. Let $𝒫$ be a typical predicate that one encounters in (non-linear) computational geometry. The general approach has three main steps:

1. Identify the symmetries of the problem, i.e. the transformations on the entries $X$ of $𝒫$ that leave invariant the output of the predicate. These transformations can be modeled by the action $\psi$ of a group $G$ operating on $X$.

2. Use appropriate techniques or known theorems to obtain polynomial invariants for $\psi$. In particular, we have investigated the use of an effective invariant construction method due to Grosshans et al. based on a symbolic representation of invariants.

3. Build a polynomial evaluation strategy for $𝒫$ by determining those orbits of $\psi$ that are discriminated by the invariants obtained above.

We have applied this general approach to two problems: determining the number of real lines piercing four given lines and determining when two quadrics have no real point in common. For the first problem we essentially reproduce the results obtained previously by Devillers et al. through a direct manipulation of equations. For the second we only have partial results so far.

This work is part of Guillaume Batog's PhD thesis (defended in December 2011) [12] .